class Solution {
public:
    pair<int, bool> dp[50][2][2][2];
    vector<int> arr;
    int findIntegers(int n) {
        int num = 1;
        arr.push_back(0);
        while (num <= n)
        {
            if (n & num) arr.insert(arr.begin(), 1);
            else arr.insert(arr.begin(), 0);
            num *= 2;
        }
        while (!arr.front()) arr.erase(arr.begin());
        return dfs(1, 1, 0, 1) + dfs(1, 0, 1, 0) + 1;
    }
    int dfs(int i, int flag, int free, int pre)
    {
        if (i >= arr.size() - 1) return flag;
        if (dp[i][flag][free][pre].second) return dp[i][flag][free][pre].first;
        int ans = 0;
        if (free)
        {
            ans += dfs(i + 1, flag, free, 0);
            if (!pre) ans += dfs(i + 1, 1, free, 1);
        }
        else
        {
            ans += dfs(i + 1, flag, arr[i], 0);
            if (arr[i] && !pre) ans += dfs(i + 1, 1, free, 1);
        }
        dp[i][flag][free][pre].second = 1;
        return dp[i][flag][free][pre].first = ans;
    }
};